package LeetCode.leetcode240;

import java.util.HashSet;

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0 , j = 0;
        boolean findArea = false;
        while (i < matrix.length && j < matrix[0].length) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
                j++;
            }else {
                findArea = true;
                break;
            }
        }
        if (matrix.length == matrix[0].length && !findArea) {
            return false;
        } else if (matrix[0].length > matrix.length && !findArea) {
            for (int k = 0; k < matrix.length; k++) {
                if (matrix[k][j] == target) return true;
            }
        } else if (matrix[0].length < matrix.length && !findArea) {
            for (int k = 0; k < matrix[0].length; k++) {
                if (matrix[i][k] == target) return true;
            }
        }
        if (findArea){
            for (int k = 0; k <= j; k++) {
                if (matrix[i][k] > target) { return false; }
                if (matrix[i][k] == target) return true;
            }
            for (int k = 0; k <= i; k++) {
                if (matrix[k][j] > target) { return false; }
                if (matrix[k][j] == target) return true;
            }
        }

        return false;
    }
}